#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MINDATA -10001

typedef struct HTNode* HuffmanTree;
struct HTNode {
    int weight;
    HuffmanTree left;
    HuffmanTree right;
};
typedef HuffmanTree ElementType;

typedef struct HNode* MinHeap;
typedef struct HNode {
    ElementType* data;
    int size;
    int capacity;
};


MinHeap CreateHeap ( int Maxsize ) {
    MinHeap H = (MinHeap)malloc(sizeof(struct HNode));
    H->data = (ElementType*)malloc(sizeof(ElementType)*(Maxsize+1));
    H->size = 0;
    H->capacity = Maxsize;
    return H;
}

bool HeapFull ( MinHeap H ) {
    return ( H->size == H->capacity );
}

bool HeapEmpty ( MinHeap H ) {
    return ( H->size == 0 );
}

void HeapInsert ( MinHeap H, ElementType X ) {
    if ( HeapFull(H) ) {
        printf("Heap Full\n");
        return;
    }
    int i = ++H->size;
    for ( ; H->data[i/2] < X; i/=2 ) H->data[i] = H->data[i/2];
    H->data[i] = X;
}

ElementType HeapDelete ( MinHeap H ) {
    int parent, child;
    ElementType minItem, X;
    if ( HeapEmpty(H) ) {
        printf("Heap empty\n");
        exit(0);
    }
    minItem = H->data[1];
    X = H->data[H->size--];
    for ( parent = 1; parent*2 < H->size; parent = child ) {
        child = parent*2;
        if ( ( child != H->size ) && ( H->data[child] > H->data[child+1] ) ) child++;
        if ( X < H->data[child] ) break;
        else H->data[parent] = H->data[child];
    }
    H->data[parent] = X;
    return minItem;
}

void PercDown ( MinHeap H, int p ) {
    int parent, child;
    ElementType X;
    X = H->data[p];
    for ( parent = p; parent*2 <= H->size; parent = child ) {
        child = parent * 2;
        if ( ( child != H->size ) && ( H->data[child] > H->data[child+1] ) ) child++;
        if ( X >= H->data[child] ) break;
        else H->data[parent] = H->data[child];
    }
    H->data[parent] = X;
}

void BuildHeap ( MinHeap H ) {
    int i;
    for ( i = H->size/2; i > 0; i-- ) PercDown(H,i);
}

HuffmanTree Huffman ( MinHeap H ) {
    int i, N;
    HuffmanTree T;
    BuildHeap(H);
    N = H->size;
    for ( i = 1; i < N; i++ ) {
        T = (HuffmanTree)malloc(sizeof(struct HTNode));
        T->left = HeapDelete(H);
        T->right = HeapDelete(H);
        T->weight = T->left->weight + T->right->weight;
        HeapInsert(H, T);
    }
    return HeapDelete(H);
}